Consider quadratic Diophantine equations of the form:
$x^2 - Dy^2 = 1$
For example, when $D=13$, the minimal solution in x is $649^2 – 13\times180^2 = 1$.
It can be assumed that there are no solutions in positive integers when $D$ is square.
By finding minimal solutions in $x$ for $D = \{2, 3, 5, 6, 7\}$, we obtain the following:
3^2 – 2×2^2 = 1
2^2 – 3×1^2 = 1
9^2 – 5×4^2 = 1
5^2 – 6×2^2 = 1
8^2 – 7×3^2 = 1
Hence, by considering minimal solutions in $x$ for $D \le 7$, the largest $x$ is obtained when $D=5$.
Find the value of $D \le 1000$ in minimal solutions of $x$ for which the largest value of $x$ is obtained.
In [1]:
from fractions import Fraction
# Reciprocal of (a + b*sqrt(d))
def recip(a,b,d):
D = a*a-b*b*d
return (a/D, -b/D)
# Integer part of (a + b*sqrt(d))
def intpart(a,b,d):
return int(a+b*d**.5)
def cfrac(d):
if d == int(d**.5+.5)**2:
return (0,0)
a = Fraction(0)
b = Fraction(1)
term = intpart(a,b,d)
a = a - term
p1,q1 = 1,0
p2,q2 = term,1
while p2*p2-d*q2*q2 != 1:
a,b = recip(a,b,d)
term = intpart(a,b,d)
p1,p2 = p2,p2*term+p1
q1,q2 = q2,q2*term+q1
a = a - term
return (p2,q2)
record = 0
best_n = 0
for n in range(1001):
c = cfrac(n)
if c[0] > record:
record = c[0]
best_n = n
print(best_n)
In [ ]: